package com.zzx.test.question;

import java.util.HashMap;

public class LeetCode1 {

    public static void main(String[] args) {
//        System.out.println("两数之和:" + Arrays.toString(twoSum(new int[]{2, 7, 11, 16}, 23)));
        System.out.println("无重复字符的最长子串:" + lengthOfLongestSubstring("abcabcbb"));
//        System.out.println("整数反转:" + reverse(-2147483412));
//        System.out.println("字符串转换整数:" + myAtoi("4193 with words"));
//        System.out.println("整数转罗马数字:" + intToRoman(9));
//        System.out.println("罗马数字转整数:" + romanToInt("MCMXCIV"));
//        System.out.println("最长公共前缀:" + longestCommonPrefix(new String[]{"flower","","flight"}));
//        System.out.println("删除有序数组中的重复项:" + removeDuplicates(new int[]{0}));
//        System.out.println("找出字符串中第一个匹配项的下标:" + strStr("sabwersad", "sad"));
    }

    public static int[] twoSum(int[] nums, int target) {
        if (nums.length == 2) {
            return new int[]{0, 1};
        } else {
            for (int i = 0; i < nums.length - 1; i++) {
                for (int j = i + 1; j < nums.length; j++) {
                    if (nums[i] + nums[j] == target) {
                        return new int[]{i, j};
                    }
                }
            }
            return null;
        }
    }

    public static int lengthOfLongestSubstring(String s) {
        int res = 0;
        int left = 0;
        HashMap<Character, Integer> map = new HashMap<>();
        char[] charArray = s.toCharArray();
        for (int i = 0; i < charArray.length; i++) {
            if (map.containsKey(charArray[i])) {
                left = Math.max(left, map.get(charArray[i]) + 1);
            }
            map.put(charArray[i], i);
            res = Math.max(res, i - left + 1);
        }
        return res;
    }

    public static int reverse(int x) {
        int res = 0;
        while (x != 0) {
            int n = x % 10;
            if (res > 214748364 || res == 214748364 && n > 7) {
                return 0;
            } else if (res < -214748364 || res == -214748364 && n < -8) {
                return 0;
            }
            res = res * 10 + n;
            x /= 10;
        }
        return res;
    }

    public static int myAtoi(String s) {
        s = s.trim();
        if (s.length() == 0) {
            return 0;
        }
        char c = s.charAt(0);
        int res = 0, flag, i = 0, max = 214748364, min = -214748364;
        if (c == '-') {
            flag = 1;
        } else if (c == '+') {
            flag = 2;
        } else if (c - '0' >= 0 && c - '0' <= 9) {
            flag = 3;
        } else {
            return 0;
        }
        char[] charArray = s.toCharArray();
        if (flag < 3) {
            i = 1;
        }
        for (; i < charArray.length; i++) {
            if (charArray[i] >= '0' && charArray[i] <= '9') {
                int n = flag == 1 ? '0' - charArray[i] : charArray[i] - '0';
                if (res > max || res == max && n > 7) {
                    res = Integer.MAX_VALUE;
                    break;
                } else if (res < min || res == min && n < -8) {
                    res = Integer.MIN_VALUE;
                    break;
                }
                res = res * 10 + n;
            } else {
                break;
            }
        }
        return res;
    }

    public static String intToRoman(int num) {
        StringBuilder stringBuilder = new StringBuilder();
        String[] strings = new String[]{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        int[] ints = new int[]{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        for (int i = 0; i < strings.length; i++) {
            int n = num / ints[i];
            stringBuilder.append(strings[i].repeat(Math.max(0, n)));
            num %= ints[i];
        }
        return stringBuilder.toString();
    }

    public static int romanToInt(String s) {
        if (s.length() == 1) {
            return getValue(s.charAt(0));
        }
        int res = 0, preNum = getValue(s.charAt(0));
        int length = s.length();
        for (int i = 1; i < length; i++) {
            int num = getValue(s.charAt(i));
            if (preNum < num) {
                res -= preNum;
            } else {
                res += preNum;
            }
            preNum = num;
        }
        res += preNum;
        return res;
    }

    public static int getValue(char c) {
        return switch (c) {
            case 'M' -> 1000;
            case 'D' -> 500;
            case 'C' -> 100;
            case 'L' -> 50;
            case 'X' -> 10;
            case 'V' -> 5;
            case 'I' -> 1;
            default -> 0;
        };
    }

    public static String longestCommonPrefix(String[] strs) {
        if (strs.length == 1) {
            return strs[0];
        }
        StringBuilder res = new StringBuilder();
        char tmp = 0;
        int index = 0;
        outer:
        while (true) {
            for (int i = 0; i < strs.length; i++) {
                if (index != strs[i].length() && i == 0) {
                    tmp = strs[i].charAt(index);
                } else if (index == strs[i].length() || tmp != strs[i].charAt(index)) {
                    break outer;
                }
            }
            index++;
            res.append(tmp);
        }
        return res.toString();
    }

    public static int removeDuplicates(int[] nums) {
        int left = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1]) {
                for (int j = left; j < nums.length; j++) {
                    if (nums[j] > nums[i]) {
                        break;
                    }
                    nums[j] = nums[i];
                }
                left++;
            }
        }
        return left;
    }

    public static int strStr(String haystack, String needle) {
        for (int i = 0; i < haystack.length() - needle.length() + 1; i++) {
            boolean flag = true;
            for (int j = 0; j < needle.length(); j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return i;
            }
        }
        return -1;
    }

}
